package pprg.mergesort;

public class MergeSortSequential {

	public int[] values; // array to be sorted
	private int[] temp; // help array

	public int[] getValues() {
		return values;
	}

	public void sorting(int[] values) {
		
		// array must have at least one element
		if (values == null || values.length == 0) {
			return;
		}

		this.values = values;
		int count = values.length;

		// new help array
		this.temp = new int[count];

		mergesort(0, count - 1);
	}

	private void mergesort(int left, int right) {
		// check if left is lower then right, if not no sorting is needed
		if (left < right) {

			// divide into to halves
			int middle = left + (right - left) / 2;

			// sorting left part
			mergesort(left, middle);

			// sorting right part
			mergesort(middle + 1, right);

			// merging the parts
			merge(left, middle, right);
		}
	}

	private void merge(int left, int middle, int right) {

		// add left and right part to temp array
		for (int i = left; i <= right; i++) {
			temp[i] = values[i];
		}

		int i = left;
		int j = middle + 1;
		int k = left;

		// smallest values of each parts to the original array
		while (i <= middle && j <= right) {
			if (temp[i] <= temp[j]) {
				values[k] = temp[i];
				i++;
			} else {
				values[k] = temp[j];
				j++;
			}
			k++;
		}

		// rest of the left part to sorted array
		while (i <= middle) {
			values[k] = temp[i];
			k++;
			i++;
		}
	}
}
